package net.aetherial.context.grounding.estimators;

import java.util.*;

import net.aetherial.context.grounding.annotators.*;
import net.aetherial.context.grounding.utilities.*;

/**
 * Generates estimates of conversational / lexical overlap term skewedness.
 */

public class ConversationalAlignmentEstimator extends Estimator
{
	private static int DEFAULT_MEMORY_SIZE = 10;
	private static double DEFAULT_CUTOFF = 0.5;
	private static Map<String, Double> cachedScores;
	
	private List<String> pastConversations;
	private int memorySize;
	private double cutoff;

	/**
	 * Returns "AlignmentEstimator".
	 * 
	 * @see net.aetherial.context.grounding.estimators.Estimator#getName()
	 */
	
	public String getName() 
	{
		return "AlignmentEstimator";
	}

	/**
	 * Generates an estimate using the layer produced by the <code>PunctuationStrippingAnnotator</code>.
	 * 
	 * @see net.aetherial.context.grounding.estimators.Estimator#estimate(java.util.Map)
	 */
	
	public double estimate (Map<String, Map<String, Object>> layers)
	{
		Map<String, Object> layer = layers.get ((new PunctuationStrippingAnnotator ()).getLayerName ());

		String sender = (String) layer.get (SENDER_KEY);
		String contribution = (String) layer.get (CONTRIBUTION_KEY);
		Double score = (Double) layer.get (SCORE_KEY);

		return this.estimate (sender, contribution, score);
	}

	/**
	 * Constructor
	 */
	
	public ConversationalAlignmentEstimator ()
	{
		super ();

		pastConversations = new ArrayList<String> ();

		try
		{
			String size = System.getProperty ("Memory Size");

			if (size == null)
				throw new NullPointerException ();

			memorySize = Integer.parseInt (size);
		}
		catch (Exception e)
		{
			memorySize = DEFAULT_MEMORY_SIZE;
		}

		try
		{
			String size = System.getProperty ("Cutoff");

			if (size == null)
				throw new NullPointerException ();

			cutoff = Double.parseDouble (size);
		}
		catch (Exception e)
		{
			cutoff = DEFAULT_CUTOFF;
		}
	}

	/**
	 * Constructor. Initializes the estimator with a memory size (count of previous conversational turns to store) and a cutoff to calculate the 
	 * skew proportion.
	 *  
	 * @param size		Number of previous turns to store.
	 * @param cut		Cutoff proportion. The estimate returned will be proportion of the area of the sorted term histogram to the left of the cutoff point.
	 */
	
	public ConversationalAlignmentEstimator (int size, double cut)
	{
		super ();

		pastConversations = new ArrayList<String> ();
		memorySize = size;
		cutoff = cut;
	}

	/*
	 * LCS algorithm adapted from:
	 * 	http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring
	 */

	private Map<String, Integer> getGCSDictionary (List<String> pastConversations2)
	{
		HashMap<String, Integer> dict = new HashMap<String, Integer> ();

		ArrayList<String> testStrings = new ArrayList<String> ();
		testStrings.addAll (pastConversations2);

		while (testStrings.size () > 0)
		{
			String lcs = findLongestCommonSubstring (testStrings);
			
			if (lcs != null)
			{
				ArrayList<String> old = new ArrayList<String> ();
				ArrayList<String> fresh = new ArrayList<String> ();

				int count = 0;

				for (String s: testStrings)
				{
					String[] mods = wordsSplit (s, lcs);

					String newString = "";

					for (String mod: mods)
					{
						if (newString.equals (""))
							newString = mod;
						else
							newString += " " + mod;
					}

					if (mods.length != 1 || mods[0].length() != s.length ())
						count += (s.length () - newString.length()) / lcs.length ();

					for (String mod: mods)
					{
						mod = mod.trim ();
						if (! (mod.equals("")))
							fresh.add (mod);
					}

					old.add (s);
				}

				if (count > 0)
					dict.put (lcs, new Integer (count));

				testStrings.removeAll (old);
				testStrings.addAll (fresh);
			}
			else
				testStrings.removeAll (testStrings);
		}

		return dict;
	}

	private ArrayList<String> getSortedKeys (Map<String, Integer> dict)
	{
		HashMap<String, Integer> testDict = new HashMap<String, Integer> ();

		for (String key: dict.keySet ())
			testDict.put (key,dict.get (key));
		
		ArrayList<String> sortedKeys = new ArrayList<String> ();

		while (testDict.size ()  > 0)
		{
			double maxScore = 0.0;
			String maxKey = null;

			for (String s: testDict.keySet ())
			{
				double score = calculateScore (s, testDict.get (s).intValue ());

				if (score >= maxScore)
				{
					maxScore = score;
					maxKey = s;
				}
			}

			sortedKeys.add (maxKey);

			testDict.remove (maxKey);
		}

		return sortedKeys;
	}

	private synchronized double calculateScore (String s, int frequency) 
	{
		if (cachedScores == null)
			cachedScores = new HashMap<String, Double> ();
		
		Double d = cachedScores.get (s);

		if (d == null)
		{
			Double f = new Double (EnglishWordFrequencies.getFrequency (s));

			d = new Double (1.0 - Math.pow (f.doubleValue (), (1.0/((double) frequency))));
			
			if (d.doubleValue () < 0)
				throw new RuntimeException ("Score too small: " + s + " / " + d);

			cachedScores.put (s, d);
		}
		
		return d;
		
	}

	private static String[] wordsSplit (String s, String lcs) 
	{
		ArrayList<String> mods = new ArrayList<String> ();

		String[] lcsArray = lcs.split (" ");
		String[] sArray = s.split (" ");

		for (int i = 0; i < sArray.length; i++)
		{
			boolean found = false;

			if (lcsArray.length + i <= sArray.length)
			{
				found = true;

				for (int j = 0; j < lcsArray.length && found == true; j++)
				{
					if (!(sArray[i+j].equals (lcsArray[j])))
						found = false;
				}
			}

			if (found)
			{
				for (int j = 0; j < lcsArray.length; j++)
					sArray[i + j] = null;

				i += lcsArray.length;
			}
		}

		String current = null;

		for (int i = 0; i < sArray.length; i++)
		{
			if (sArray[i] != null)
			{
				if (current == null)
					current = sArray[i];
				else
					current += " " + sArray[i];
			}
			else
			{
				if (current != null)
				{
					mods.add(current);
					current = null;
				}
			}
		}

		if (current != null)
			mods.add (current);

		String a[] = new String[mods.size ()];

		for (int i = 0; i < mods.size(); i++)
			a[i] = mods.get (i);

		return a;
	}

	private static String findLongestCommonSubstring (Collection<String> strings)
	{
		String lcs = null;
		for (String s: strings)
		{
			for (String t: strings)
			{
				if (s != t)
				{
					String clcs = findLongestCommonSubstring  (s, t);

					if (clcs != null)
					{
						if (lcs == null)
							lcs = clcs;
						else if (clcs.length () > lcs.length ())
							lcs = clcs;
					}
				}
			}
		}

		return lcs;
	}

	/* private static String pretty (Object[] ss)
	{
		String out = "[ ";

		for (Object s: ss)
			out += s + ", ";

		out += " ]";

		return out;
	} */

	private static String findLongestCommonSubstring (String s, String t) 
	{
		ArrayList<String> substring = new ArrayList<String> ();

		String lcs = null;

		String[] sWords = s.split (" ");
		String[] tWords = t.split (" ");

		if (!(s == null || t == null || sWords.length == 0 || tWords.length == 0))
		{
			int[][] num = new int[sWords.length][tWords.length];

			int maxlen = 0;
			int lastSubsBegin = 0;

			for (int i = 0; i < sWords.length; i++)
			{
				for (int j = 0; j < tWords.length; j++)
				{
					if (!(sWords[i].equals (tWords[j])))
						num[i][j] = 0;
					else
					{
						if (i == 0 || j == 0)
							num[i][j] = 1;
						else
							num[i][j] = 1 + num[i-1][j-1];

						if (num[i][j] > maxlen)
						{
							maxlen = num[i][j];
							int thisSubsBegin = i - num[i][j] + 1;

							if (lastSubsBegin == thisSubsBegin)
								substring.add (sWords[i]);
							else
							{
								lastSubsBegin = thisSubsBegin;

								substring.removeAll (substring);

								for (int k = lastSubsBegin; k < (i + 1) - lastSubsBegin; k++)
									substring.add (sWords[i]);
							}

						}
					}
				}
			}
		}

		for (String word: substring)
		{
			if (lcs == null)
				lcs = "";
			else
				lcs += " ";

			lcs += word; 
		}

		return lcs;
	}

	/**
	 * @see net.aetherial.context.grounding.estimators.Estimator#estimate(java.lang.String, java.lang.String, double)
	 */
	
	public double estimate (String sender, String contribution, double score) 
	{
		pastConversations.add (contribution);

		while (pastConversations.size () > memorySize)
			pastConversations.remove (0);
		
		Map<String, Integer> dict = this.getGCSDictionary (pastConversations);
		ArrayList<String> sortedKeys = this.getSortedKeys (dict);

		double left = 0.0;
		double total = 0.0;
		
		for (int i = 0; i < sortedKeys.size (); i++)
		{
			String key = sortedKeys.get (i);

			double keyScore = this.calculateScore (key, dict.get (key).intValue ()); 

			if (i < ((double) sortedKeys.size ()) * cutoff)
				left += keyScore;
				
			total += keyScore;
		}

		if (total == 0.0)
			return total;
		
		double proportion = left / total;

		double estimate = (proportion - cutoff) / cutoff;
		
		return estimate;
	}
}
